package mysql8学习.高级.第06章_索引的数据结构;

/**
 * AVL数
 * 为了解决上面二叉查找树退化成链表的问题，
 * 人们提出了平衡二叉搜索树(Balanced Binary Tree)
 * 又称为AVL树(有别于AVL算法)
 * 它在二叉搜索树的基础上增加了约束，具有以下性质:
 * ● 它是一棵空树或它的左右两个子树得高度差的绝对值不超过1,
 *   并且左右两个子树都是一棵平衡二叉树。
 *
 * 这里说一下，常见的平衡二叉树有很多种，
 * 包括了 平衡二叉搜索树、红黑树、数堆、伸展树。
 * 平衡二叉搜索树  是最早提出来的 自平衡二叉搜索树，
 * 当我们提到平衡二叉树时一般指的就是平衡二叉搜索树。
 * 事实上，第一棵树就属于平衡二叉搜索树，搜索时间复杂度就是O(1og2n)。
 *
 * 数据查询的时间主要依赖于磁盘I/O的次数,如果我们采用二叉树的形式，
 * 即使通过平衡二叉搜索树进行了改进，树的深度也是0(log2n),
 * 当n比较大时，深度也是比较高的
 *
 * 把树变得矮胖   进行的I/O就会更少
 * 比如变成   平衡三叉树   平衡四叉树.....平衡N叉树
 * 就引出了  b树
 *
 */
public class J4_AVL数 {
}
